package unionFindStudy;

public class UnionFindStudy03 {

    /**
     * 在本问题中, 树指的是一个连通且无环的无向图。
     *
     * 输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
     *
     * 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
     *
     * 返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
     *
     * @param args
     */
    public static void main(String[] args) {

    }

    public static int[] findRedundantConnection(int[][] edges){
        int len = edges.length;
        UnionFind unionFind = new UnionFind(len);
        for (int i = 0; i < len; i++){
            int[] edge = edges[i];
            int res = unionFind.merge(edge[0]-1, edge[1]-1);
            if (res == 0){
                return edge;
            }
        }
        return null;
    }
}
class UnionFind{
    //并查集中的元素
    int[] parent;

    public UnionFind(int n){
        parent = new int[n];
        //
        for (int i = 0; i < n; i++){
            parent[i] = i;
        }
    }

    //合并 1 - successfully  0 - failed
    public int merge(int index1, int index2){
        //查询到index01的帮主
        int index1_root = find(index1);
        //查询到index02的帮主
        int index2_root = find(index2);
        if (index1_root == index2_root){
            //失败返回0
            return 0;
        } else {
            parent[index2_root] = index1_root;
            return 1;
        }
    }

    public int find(int index){
        //查找时同时优化并查集的结构
        return parent[index] == index?index:(parent[index]=find(parent[index]));
    }
}
